\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{wrapfig}
\usepackage[vlined,lined,linesnumbered,boxed,french,longend]{algorithm2e}
\usepackage{xcolor}
\usepackage[top=2.5cm, bottom=2.5cm, left=2cm, right=2cm]{geometry}
\usepackage{lmodern}
\usepackage{enumerate}
\usepackage{verbatim}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,shapes}


\usepackage{fancyhdr}
\lhead{\bsc{Projet OS}}
\rhead{\bsc{Ordonnanceur de threads}}
\renewcommand{\headrulewidth}{1px}
\lfoot{ \bsc{Enseirb-Matmeca}}
\rfoot{ \bsc{Informatique-I2}}
\renewcommand{\footrulewidth}{1px}
\pagestyle{fancy}
%fin
\begin{document}
\clearpage
\vspace*{\stretch{1}}
\begin{center}
{\huge Projet Sytème d'exploitation}\\
{\footnotesize Ordonnanceur de threads}\\
~\\
{\large Julien \bsc{Drecq}\\ Mehdi \bsc{Ouidani}\\ Mohamed \bsc{Akdim} \\ Saad-eddine \bsc{Elmernissi} \\Yannick \bsc{Levif}}
\end{center}
\vspace*{\stretch{1}}


\begin{center}
\today
\end{center}

\newpage

\newpage
\tableofcontents
\newpage

\section{Introduction}
	
Ce projet vise à construire une bibliothèque de threads en espace utilisateur.
L'objectif est de fournir une interface de programmation plus ou moins proche des pthreads. Les intérêts sont:

\begin{itemize}
\item Les coûts d'ordonnancement sont beaucoup plus faibles
\item Les politiques d'ordonnancement sont configurables
\end{itemize}
  
Nous présenterons ici, les fonctionnalités implémentées et fonctionnelles ainsi que nos démarches et nos reflexions sur celles non fonctionnelles.
On analysera ensuite les performances de notre bibliothèque sur diffèrentes fonctions et les comparer à celles de l'API pthread.

Au commencement, nous devions réfléchir à la structure de nos threads et comment tenir compte du fait que le \"main\" devait être traité comme un thread ordinaire.
Ensuite, nous devions implémenter les fonctions basiques d'ordonnancement basiques pour des threads pour ensuite aller plus loin et ajouter certaines fonctionnalités avancées.

\section{La structure thread}


\begin{verbatim}
struct Thread {
  ucontext_t * context;

  void * (*func)(void*);
  void * arg;
  void * resultat;

  int priorite;
  int priorite_actuelle;

  int ID;
  int termine;

  func_sig fonctions_sig[NB_SIG];;
  GList * signal_attente;

  int valgrind_stackid;
};
\end{verbatim}

Nous devions au préalable réfléchir à la structure générale de nos threads. Elle devait tenir compte de chaque fonctionnalité necessaire à leur fonctionnement.\\
Tout d'abord, un thread devait pouvoir utiliser un contexte qui lui était propre, d'où la présence du champ \verb 'context' qui nous sert à stocker le contexte du thread.\\
Ensuite, il fallait reconnaitre un thread d'un autre, afin de mieux distinguer le thread \"main\" des autres. C'est pourquoi nous introduisons le champ \verb 'ID'. Celui-ci sera egal à 0 si il s'agit du thread \"main\". Mais il faut savoir que l'on aurait pu supprimer ce champ et distinguer les threads par leur adresse, mais nous preferons laisser ce champs pour avoir une meilleure visibilité sur le problème et ainsi être plus clair.\\
Nous devons savoir egalement si un thread à réellement terminer son execution. Le champ \verb 'termine' nous le permettra : sa valeur sera de 0 lorsque le thread sera toujours en execution et 1 si ce dernier à fini son execution. Ce champ est essentiel car nous n'utilisons qu'une seule liste pour gérer les diffèrents thread (detail plus bas).\\
\verb 'valgrind_stackid' permet simplement à valgrind d'indiquer les allocations et desallocations de mémoire.
Il faut savoir qu'au debut nous n'avions pas ce champs. Nous verifions la terminaison d'un thread par son appartenance à la la liste de stockage des threads. Mais pour que nos focntions soit plus rapides et que le parcours d'une liste est longue, nous avons décider d'introduire ce champ à la structure de nos threads.\\
Pour finir les champs \verb 'func', \verb 'arg', \verb 'resultat'  nous permettent de stocker la fonction devant être executée par le thread concerné. De plus nous stockons les arguments et la valeur de retour de celle-ci. Ces champs nous permettrons alors d'executer une fonction de thread sans appeler \verb 'thread_exit' à la fin.\\\\
Les champs restant sont utils pour les fonctionnalités avancées et n'ont donc été ajoutés que par la suite.\\
Les champs \verb 'priorite' et \verb 'priorite_actuelle' nous servirons à trier dans la liste les threads en fonction de leur priorité. Nous detaillerons plus loin comment nous gérons ces priorités.\\
Enfin les champs \verb 'fonctions_sig' et \verb 'signal_attente' servent à gérer les signaux destinés à nos threads. De même nous detaillerons leurs utilités plus loin dans le rapport.\\
\\
Après avoir défini cette structure, nous devons maintenant savoir comment gérer nos threads.

\section{Gestion des threads}

Tout d'abord pour faciliter la gestion des threads, nous utilisons les threads comme des pointeurs : \verb 'typedef struct thread * Thread'. Ainsi nous pouvons utiliser une seule liste \verb 'waitingThreads' pour nos threads. Les threads sur lesquels nous n'avons toujours pas appelés \verb 'thread_join' ne feront plus partis de cette liste. Par contre nous pourrons avoir de nouveau accés à la zone mémoire du thread par le fait que \verb 'Thread' soit un pointeur caché.\\
Nous définissons également une autre variable globale : \verb 'runningThread' qui correspond au thread étant executé. Il faut savoir que de nouveau cette variable globale peut être inutile si nous considérons le thread executant comme le premier thread de notre liste. Mais ceci impliquerait une moins bonne clarté du code et une difficulté supplémentaire lors des tris de la liste.\\
Au depart, la liste était gérée comme une pile FIFO. Mais nous avons pu implémenter un système de priorités. Ceci permet donc à certain thread d'être executer plus de temps que d'autre. Nous détaillerons l'implementation des priorités plus loin.\\
Donc ici, la gestion des threads se résume à la gestion d'une liste.

\section{Fonctionnalités implémentées}
\subsection{Création et exécution des threads}

\begin{verbatim}
Thread * thread_self (void);
\end{verbatim}\\
Avec notre choix d'implémentation, cette fonction renvoie simplement le pointeur \verb'runningThread'.

\begin{verbatim}
int thread_create (Thread *, void *(* func)(void *), void *);
\end{verbatim}

Cette fonction nous permet de créer un thread. Tout d'abord, nous verifions par l'intermediaire de la variable globale \verb 'nextID' si le thread correspondant au `\"main\" a déjà été crée. En effet si le main n'a pas été crée, \verb 'nextID' sera egal à 0. Ensuite on crée simplement un thread que l'on initialise avec des valeurs par default que l'on execute dès la fin de son initialisation grâce à la fonction suivante.

\begin{verbatim}
void thread_start (Thread);
\end{verbatim}
Cette fonction vérifie tout d'abord si le thread en execution a fini son execution grâce au champ \verb 'termine'. Si oui alors à \verb 'runningThread' on attribut simplement la tête de la liste \verb 'waitingThreads', autrement on l'ajoute à la fin de cette dernière.
Il faut savoir que l'on execute un thread au niveau utilisateur, donc nous utilisons les contextes pour l'execution de threads. Par consequent un thread est executé par un \verb 'swapcontext'.

\subsection{Ordonnancement}
\begin{verbatim}
void thread_yield (void);
\end{verbatim}
Cette fonction est, on ne peut plus simple grâce à l'implementation de notre fonction \verb 'thread_start'. En effet, cette fonction se chargera simplement d'appeler \verb 'thread_start' sur le premier élément de \verb 'waitingThreads' seulement si la liste est non nulle.

\begin{verbatim}
int thread_join (Thread *, void **);
\end{verbatim}
La fonction certainement la plus importante car elle nous permettra ici de \verb 'free' les threads concernés, donc à l'appel de la fonction nous avons toujours accés à la zone mémoire du thread. Ce thread ne se trouve plus dans notre liste mais le \verb 'Thread' est un pointeur caché. Nous vérifions d'abord si le thread concerné a fini son execution. Si oui nous attribuons la valeur de retour de la fonction du thread stockée dans le champs de la structure \verb 'resultat' à l'argument de type \verb 'void **' de \verb 'thread_join' puis nous liberons les zones mémoires occupés. Sinon, nous executons le thread tant qu'il n'est pas terminé.

\subsection{Fin d'exécution}

Au debut, nous devions toujours appeler la fonction suivante à la fin des fonctions attribuées à un thread :

\begin{verbatim}
void thread_exit (void *);
\end{verbatim}

Mais pour pouvoir finir l'execution d'un thread sans toujours appeler cette dernière fonction, nous attribuons en réalité une fonction annexe de notre bibliothèque au contexte du thread: \verb 'void exec_func (void)'.
Cette dernière executera la vraie fonction associée au thread par l'utilisateur stockée dans le champs \verb 'func' avec les arguments stockés dans  \verb 'arg' et enfin stocker la valeur de retour de cette fonction dans \verb 'resultat'.
Ainsi un nous évitons à l'utilisateur d'appeler à chaque fois \verb 'thread_exit'.


\section{Fonctionnalités avancées}

Après avoir implémenté ces fonctions de gestion basique de nos threads, nous devons aller plus loin et chercher à generaliser nos threads et donner accés à encore plus de focntionnalité à l'utilisateur. Au debut, nous avons eu du mal à commencer. Nous ne savions pas quelle fonctionnalité à choisr. Au final après s'être penché sur les diffèrents problèmes, nous avons pu implémenter les fonctionnalités avancées suivantes :

\begin{itemize}
\item La gestion des signaux
\item La gestion des priorités
\item La préemption
\item La detection de debordement de pile
\end{itemize}


\subsection{Signaux}

\subsubsection{Principe}

Tout d'abord on a définit diffèrents signaux tel que SIG_YIELD, SIG_KILL ou SIG_USR1. Il existe 4 signaux utilisateurs (SIG_USR). Nous disposons donc de 6 signaux de type diffèrents.
Les champs \verb 'fonctions_sig' et \verb 'signal_attente' de notre structure thread nous sont desormais utils.

\verb 'fonctions_sig' nous permet de définir un comportement pour un signal donné. Ce champ est donc un tableau de 6 pointeurs de fonctions. A l'initialisation nous attibuons un comportement par défault aux signaux : Si on reçoit un SIG_KILL on execute \verb 'thread_exit', si on reçoit un SIG_YIELD on execute \verb 'thread_yield', sinon on affiche simplment le numero du signal. Par contre il faut faire attention à l'envoi du signal SIG_KILL car on execute \verb 'thread_exit' sans se préoccuper du fait que le thread pourrait avoir créer des threads fils. Il se pourrait alors que notre bibliothèque bloque.
Puisque nos threads s'executent en mode cooperatif, l'un après l'autre, on ne peut pas traiter directement lors de sa reception un signal. C'est pourquoi le champ \verb 'signal_attente' existe. Un signal envoyé sera stocké dans cette liste. Cette dernière représente donc les signaux reçus par le thread et encore non traitée. On s'arrange alors pour traiter ces signaux lors des appels de \verb 'thread_start'.

Nous avons donc mis à disposition des fonctions permettant de manipuler 


\subsubsection{Fonctions}

\verb 'thread_kill' est la fonction permettant d'envoyer un signal. Cette fonction prends en parametre le thread de destination et le signal à envoyer. Elle se chargera alors de chercher le thread destinataire dans notre liste d'attente. Ensuite il rajoutera le signal au champs \verb 'signal_attente'. Ainsi le signal sera traiter plus tard lors de l'appel de la fonction \verb 'thread_signal_treat'.

\verb 'thread_signal_treat' se charge simplement de traiter les signaux du thread en paramètre en appelant les fonctions correspondantes et vide la liste des signaux en attente.

\verb 'thread_signal_alloc' définit un comportement pour un signal donné. Ainsi l'utilisateur pourra définir lui-même le comportement d'un signal. La fonction modifiera donc le champ \verb 'fonctions_sig' du thread placé en paramètre en introduisant la fonction entrée en paramètre.

En donnant accés à l'utilisateur à la fonction \verb 'thread_signal_treat' nous lui donnons la possibilité de choisir les moment pendant lesquels il pourra traiter les signaux. Ainsi il pourra avoir une reception de signaux plus performante.


\subsubsection{Ameliorations}

Pour améliorer la gestion des signaux, nous pourrions tout d'abord sécuriser le traitement par default du signal SIG_KILL afin d'éviter les problèmes pendant la création récursive de threads.
De plus nous pourrions faire en sorte de pouvoir traiter un signal de manière \"immediate\". Mais pour cela il faudrait pouvoir faire tourner nos threads en parallèle sur des threads noyaux. 

Mais le gestionnaire basique des signaux a été implémenté avec succès et est focntionnel.

\subsection{Les priorités}

Lors de l'introduction des priorités, notre liste \verb 'waitingThreads' n'est plus une FIFO. En effet, nous trions desormais les threads en fonction de leur priorité. Ainsi les threads qualifié d'importants seront executés plus fréquemment que les autres.
Ici nous considerons que toutes les priorités sont positives. De plus, nous avons considérés que plus la valeur d'une priorité est haute plus elle est importante. Par exemple, une priorité de 100 est plus importante qu'une priorité de 0.

Nous définissons la priorité d'un thread dans le champ \verb 'priorite' de notre structure thread. Mais le problème est que si cette priorite ne change pas, alors on risque de constamment executer le thread ayant la priorité la plus haute. Il a donc fallu trouver une solution pour executer également les autres threads. Pour se faire, nous avons définit le champ \verb 'priorite_actuelle' qui nous permet de faire varier la priorité des threads. Ainsi à la fin de chaque execution d'un thread (donc à chaque appel de \verb 'thread_start') nous décrementons la valeur de \verb 'priorite_actuelle'. Si cette dernière est negative ou nulle, nous la remettons à la valeur initiale, à savoir \verb 'priorite'.
Il faut savoir que tri de notre \verb 'waitingThreads' se fait grâce à la bibliothèque GLib.

Pour introduire les priorites lors de la creation d'un thread, nous mettons à disposition à l'utilisateur une nouvelle fonction : \verb 'thread_create_prio'. Ainsi le dernier argument representera la priorité que l'utilisateur voudra attribuer à son thread. Il faut savoir que \verb 'thread_create' définit une priorité par défault de 20.

Le système de priorité peut être interessante à implementer si nous avons implementé la préemption.

\subsection{La préemption}

Le système de préemption est très interessant à implementer. La préemption consiste à laisser un thread s'executer seulement pendant un court lapse de temps (les Timeslices). Mais il faut savoir qu'en fonction des priorités des threads, ce temps d'execution pourra varier.

Ainsi pour implémenter la préemption, nous devions implémenter une alarme qui nous permettrait de nous signaler quand nous devions changer de thread.

\subsubsection{Alarme virtuelle}

Ainsi nous utilisons la fonction \verb 'setitimer' qui est utile car cette alarme peut être configurée pour se répéter. Il faut savoir que cette fonction envoie à chaque intervalle de temps un signal SIGVTALRM. Ainsi il faut mettre en place une fonction gérant ce signal avec \verb 'sigaction'. Ainsi à chaque signal, nous appellerons simplement \verb 'thread_yield'. 

\subsubsection{Bloquer les alarmes}

Mais un problème persiste, si nous définissons un intervalle trop court, il se peut qu'il y ait des problèmes lors de \verb 'thread_yield'. En effet, on receptionnerait un signal SIGVTALRM et devons effectuer un \verb 'thread_yield'. Nous avons donc un cercle vicieux d'appel de fonction se repetant autant de fois que l'alarme se déclenche, c'est à dire presque infiniment.

Pour remédier à cela, nous définissons 2 fonctions \verb 'block()' et \verb 'unblock()' qui nous permettent de bloquer les signaux et de les débloquer. Ainsi à chaque appel de fonctions importantes de notre ordonnanceur, nous appelons \verb 'block()' au début de la zone critique et \verb 'unblock()' à la fin.

Mais ici, nous gerons mal le signal reçu. En effet, à chaque traitement de SIGVTALRM nous obtenons une erreur. Nous avons donc mis de coté ce code.


\subsection{La detection de debordement de pile}

La detection de debordement de pile est difficil à mettre en place. Il faut d'abord comprendre le comportement de la fonction \verb 'mprotect' et gérer le signal SIGSEGV.
Tout d'abord, on ajuste la memoire alloué pour un contexte aux pages du système grâce à \verb 'memalign'. On peut récupérer la taille d'une page système grâce à \verb 'sysconf(_SC_PAGE_SIZE)'. Ensuite on fait appel à \verb 'mprotect' pour la detection de debordement. Nous considerons que le thread peut lire ou modifier ce qui est présent dans la zone mémoire et qu'il peut y avoir des executables dans cette zone.

Lors de la recption d'un SIGSEGV, nous quittons simplement le thread executant.

Mais cette focntionnalité n'étant pas compléte et son comportement étant inconnu, nous avons décidé de le mettre à l'ecart dans notre code.

\section{Comparaison de performances avec pthread.h}

Nous avons ensuite pris l'initiative de tester les performances des focntionnalités focntionnelles de notre bibliothèque par rapport à celles de pthread. Nous avons donc executé plusieurs programme et mesuré leur temps d'execution.

\subsection{Fibonacci}

Nous avons d'abord choisi le programme Fibonacci. En premier lieu nous testons les limites des bibliothèques. Avec pthread, on ne peut pas calculer fibonacci pour une valeur de plus de 14, alors que thread.h peut aller jusqu'à 28 sans erreurs avec cette taille de pile. Si nous augmentons la taille de la pile du contexte de nos threads, nous pouvons alors aller plus loin dans la suite de fibonacci. Mais avec des temps d'éxecution exponentiellement croissant, nous n'avons pas pu tester la valeur limite avec une pile plus importante.


GRAPHE

Nous pouvons remarquer que le temps d'execution avec la bibliothèque pthread est largement superieur.

\subsection{switch_many}

\subsection{create_many_recursive}

\section{Conclusion}

En conclusion, nous avons implémenté une bibliothèque de threads fonctionnelle. Elle nous permet d'executer certaine tache plus rapidement que pthread. Mais elle possède également ses limites. En effet, les threads sont toujours executés les uns après les autres et ne permet pas d'effectuer 2 threads au même moment. Ce qui aurait pu améliorer le temps d'execution  pour certaines applications.

Nous avons alors réussi à implementater quelques fonctionnalités avancés mais il sera necessaire de les améliorer et les optimiser. De plus certaines ne sont pas encore fonctionnelles, il serait bien alors d'approfondir les recherches sur les causes de ce non-fonctionnement...
Enfin, il aurait été interessant d'implémenter le fait d'utiliser plusieurs thread noyaux pour executer plusieurs de nos threads au même moment.

\end{document}